package com.linyaonan.leetcode.easy._783;

import java.util.ArrayList;
import java.util.List;

/**
 *
 * 给定一个二叉搜索树的根结点 root, 返回树中任意两节点的差的最小值。
 *
 * 示例：
 *
 * 输入: root = [4,2,6,1,3,null,null]
 * 输出: 1
 * 解释:
 * 注意，root是树结点对象(TreeNode object)，而不是数组。
 *
 * 给定的树 [4,2,6,1,3,null,null] 可表示为下图:
 *
 *           4
 *         /   \
 *       2      6
 *      / \
 *     1   3
 *
 * 最小的差值是 1, 它是节点1和节点2的差值, 也是节点3和节点2的差值。
 * 注意：
 *
 * 二叉树的大小范围在 2 到 100。
 * 二叉树总是有效的，每个节点的值都是整数，且不重复。
 *
 *
 * @author: Lin
 * @date: 2020/1/16
 */
public class MinimumDistance {
    int min = Integer.MAX_VALUE;
    List<Integer> save;
    public int minDiffInBST(TreeNode root) {
        save = new ArrayList<>();
        dfs(root);
        for (int i = 0; i < save.size() - 1; i++) {
            min = Math.min(save.get(i) - save.get(i+1), min);
        }
        return min;
    }

    private void dfs(TreeNode node) {
        if (node != null) {
            dfs(node.right);
            save.add(node.val);
            dfs(node.left);
        }
    }

}
